/*
TODO:
 + wczytywanie grup z pliku groups.dat
 + struktura danych do przechowywania grup
    + tablica list studentow, indeksowana numerem grupy
    + odwzorowanie studento-przedmiotu na numer grupy, 0 -- przedmiot nie
      jest grupowy lub koles nie jest w grupie
 - uwzglednienie grupy w algorytmie: przy generowaniu poczatkowych rozwiazan
   i przy kazdej modyfikacji, dokładniej:
    + void solution_init_random(int**);
    + void pheromone_improve(Ant& ant, double risk_const, int rep_count);
      [brak zmian]
    + void local_search(Ant& ant);
      [brak zmian]
 ? rozdzielenie w ww. funkcjach funkcjonalnosci zwiazanych z zapisywaniem
   pojedynczego studenta i calej grupy
 + pytanie: zezwalac na rozwiazania bez uwzglednienia podzialu na grupy?
    * sugestia: nie -- mogloby byc sporo rozwalonych grup, doszedlby dodatkowy
      mechanizm mieszania studentami (w celu efektywnej implementacji)
    + sugestia: tak -- algorytm moglby dawac ogolnie lepsze wyniki
 + urozmajcenie poczatkowego generowania rozwiazan przez losowanie
   kolejnosci studentow
 - zroznicowanie mrowek, mrowki bez feromonow

BUGFIX:
 + LPI było zepsute
 + term_collides: term_in != term_out => plan[stud_id][i] != term_out
 + solution_init_random nie powinno moc sie zawiesic 
 
BUGS:
*/

#include <iostream>
#include <vector>
#include <fstream>
#include <math.h>
#include <ctime>
#include <unistd.h>
#include <signal.h>
#include <cstdlib>
#include "mrowkowy.hh"

int stud_count;     //liczba studentow

int prze_count;     //liczba przedmiotow

int* term_count;    //liczba terminow na dany przedmiot

int* term_index;    //indeks pierwszego terminu danego przedmiotu

int* terms;         //liczba miejsc na poszczegolne terminy

int** pref;         //preferencje studentow co do terminow, im wyzsze, tym termino
                    //bardziej pozadany

int** stud_group;   //tablica stud_group[przedmiot][student] = grupa
                    //stud_group[przedmiot] == NULL <=> nie jest grupowy
                      
int** group;        //tablica group[grupa][0] = rozmiar, group[grupa][i] = student

int total_groups_count;  //calkowita liczba grup

int* group_count;   //liczba grup danego przedmiotu

bool** kolizje;     //macierz kolizji miedzy terminami

int terms_total = 0;    //calkowita liczba terminow

double** pheromones;    //tablica feromonow [student][termin]
            //im wyzsza wartosc, tym bardziej prawdopodobne bedzie
            //wybranie rozwiazania, gdzie 'student' jest na terminie 'termin'
                    
int pref_max;        //najwyzsza wartosc preferencji

Ant best_so_far;    //najlepsze jak do tej pory rozwiazanie

double gpi;        //global progress index - wspolczynnik postepu
                   //tj. jak bardzo poprawia najlepsze sie rozwiazanie
                    
int* stud_order;    //studenci w kolejnosci losowej, uzywane przy przeszukiwaniu lokalnym
int* stud_order2;   //studenci w innej losowej kolejnosci, jw.
int* prze_order;    //kolejnosc przedmiotow, jw.

double stable_ants_part = 0.0;	//jaka czesc mrowek bedzie z ograniczonymi feromonami
double stability_eps = 1e1; //epsilon po ktorym stabilne mrowki zachowuja sie normalnie

double copy_pro = 0.01; //prawdopodobienstwo skopiowania best_so_far do nowej mrowki

double risk_c = 1.;    //jak bardzo ryzykownie zachowuja sie mrowki, tj.
            //im wyzsza wartosc, tym wieksze prawdopodobienstwo
            //ze mrowka chwilowo wybierze gorsze rozwiazanie
            //podczas ulepszania feromonowego
                    
double gpi_mem = 0.7;    //wspolczynnik pamieci GPI, tj. waga z jaka
            //brana jest wartosc GPI w poprzedniej iteracji
            //przy obliczaniu nowej wartosci
                        
int ant_cnt = 10;    //liczba mrowek
double dominant = 10.;    //ile razy bardziej wazne jest najlepsze rozwiazanie
            //od pozostalych, przy obliczaniu macierzy feromonu
                        
double evap = 0.7;    //wspolczynnik parowania feromonu, tj. jaka czesc feromonu
            //paruje po kazdej iteracji
                        
double epsilon = 1e-5;    //gdy GPI osiagnie taka wartosc, obliczenia sa przerywane
double rand_eps = 1e-1;    //gdy LPI mrowki osiagnie taka wartosc, zostaje jej
                        //przydzielone nowe, losowe rozwiazanie
                        
int reps = 20;        //liczba iteracji ulepszania feromonowego

bool quiet = false;    //nie wypisuje zadnych informacji na stdout

const char *termfile = "terminy.dat";
const char *preffile = "pref.dat";
const char *groufile = "grupy.dat";
const char *collfile = "kolizje.dat";
const char *outfile = "plan.txt";

using namespace std;

void usage(){
    cerr << "Usage: mrowkowy [-h] [-T|P|C|G|o file] [-s|f|p|r|g|c|d|v|i|e|t num]" << endl;
    cerr << "  -h\thelp" << endl;
    cerr << "  -T\tset terms input file" << endl;
    cerr << "  -P\tset preferences input file" << endl;
    cerr << "  -C\tset collisions input file" << endl;
    cerr << "  -G\tset groups input file" << endl;
    cerr << "  -o\tset output file" << endl;
    cerr << "  -s\tpart of ants which should be stable, ie. not use pheromone search in early stages; [0,1]" << endl;
    cerr << "  -f\tepsilon after which stable ants do pheromone search; [0,oo]" << endl;
    cerr << "  -p\tprobability of copying best ant's solution to new ant" << endl;
    cerr << "  -r\thow risky the ants should be; [0,1]" << endl;
    cerr << "  -g\tset GPI-memory-const; the lower, the faster algorithm will stop; [0,1)" << endl;
    cerr << "  -c\tset ants count" << endl;    
    cerr << "  -d\tset importance of dominant ant; [0,oo]" << endl;
    cerr << "  -v\tset evaporation rate; [0,1]" << endl;
    cerr << "  -i\tnumber of pheromone improvements per iteration" << endl;    
    cerr << "  -e\twhen GPI is less than epsilon, program ends; default 1e-5" << endl;
    cerr << "  -t\ttrigger inserting some new ants when LPI < t; default 1e-1" << endl;    
    cerr << "  -q\tquiet" << endl;
    cerr << "GPI is short for Global Progress Index; the solution is improving faster, the GPI is higher. Additionaly when GPI is lower (there hasn't been any improvement recently), ants become more risky. LPI is analogous, local progress index." << endl;
    exit(1);
}

void parse_opts(int argc, char* argv[]){
    if ( argc < 2 )
	usage();
    int c;
    while ( (c = getopt(argc, argv, "T:P:C:G:o:huqr:g:c:d:v:i:e:t:s:f:p:")) != -1 ){
        switch(c){
	    case 'T': termfile = optarg; break;
	    case 'P': preffile = optarg; break;
	    case 'C': collfile = optarg; break;
	    case 'G': groufile = optarg; break;
	    case 'o': outfile = optarg; break;
            case 'h': case '?': usage(); break;
            case 's': stable_ants_part = atof(optarg); break;
	    case 'f': stability_eps = atof(optarg); break;
	    case 'p': copy_pro = atof(optarg); break;
            case 'r': risk_c = atof(optarg); break;
            case 'g': gpi_mem = atof(optarg); break;
            case 'c': ant_cnt = atoi(optarg); break;
            case 'd': dominant = atof(optarg); break;            
            case 'v': evap = atof(optarg); break;
            case 'i': reps = atoi(optarg); break;
            case 't': rand_eps = atof(optarg); break;            
            case 'e': epsilon = atof(optarg); break;
            case 'q': quiet = true; break;
            default: exit(1);
        }
    }
}

int finishing = 0; //kiedy == 1 program zapisuje wyjscie i sie konczy

void sigint_handler(int sig){
    finishing = 1;
}

// MAIN ################################
int main(int argc, char** argv){
    srand(time(NULL)+getpid()); 
    parse_opts(argc, argv);
    read_input();
    cerr << "Input read." << endl;
    int** plan; //rozklad zajec
    
    //alokacja tablicy na plan
    plan = new int*[stud_count];
    for ( int i = 0; i < stud_count; i++ )
        plan[i] = new int[prze_count];

    stud_order = new int[stud_count];
    stud_order2 = new int[stud_count];    
    prze_order = new int[prze_count];
    for ( int i = 0; i < stud_count; i++ ){
        stud_order2[i] = stud_order[i] = i;
    }
    for ( int i = 0; i < prze_count; i++ ){
        prze_order[i] = i;
    }
    
    randomize_array_order(prze_order, prze_count);
    randomize_array_order(stud_order, stud_count);
    
    Ant* ants = new Ant[ant_cnt];
    
    while(!solution_init_random(plan));
    ant_init(ants[0], plan);
    ant_init(best_so_far, plan);
    
    for ( int i = 1; i < ant_cnt; i++ ){
        while(!solution_init_random(plan));
        ant_init(ants[i], plan);
    }
    
    signal(SIGINT, sigint_handler);
    mrowkowy(ants, ant_cnt, epsilon, risk_c, gpi_mem, evap, dominant);
    save_output(best_so_far.solution);
    
    return 0;
}

// CZYTANIE WEJSCIA ####################
void read_input(){
    ifstream ter(termfile);
    ifstream pre(preffile);
    ifstream kol(collfile);
    ifstream gro(groufile);
    
    ter>>prze_count;
    ter>>terms_total;
    term_count = new int[prze_count];
    term_index = new int[prze_count + 1];
    term_index[0] = 0;
    
    terms = new int[terms_total];
    
    for ( int i = 0; i < prze_count; i++ ){
        int prze_akt;
        ter >> prze_akt;
        ter >> term_count[prze_akt]; //ilosc terminow na dany przedmiot
        //int ter_akt_count;
        //ter>>ter_akt_count;
        
        int ter_ind_akt;
        for (int j=0; j<term_count[prze_akt]; j++){
            ter>>ter_ind_akt;
            ter>>terms[ter_ind_akt];
        }
    }
    
    for ( int i = 0; i < prze_count; i++ )
        term_index[i + 1] = term_index[i] + term_count[i];
    
    pre>>stud_count;
    
//  cerr << stud_count << " " << prze_count << " " << term_index[5] << endl;
    
    pref=new int*[stud_count];
    for (int i=0; i<stud_count; i++)
        pref[i]=new int[terms_total];
        
    pref_max = 1;
    for (int i=0; i<stud_count; i++){
        int stud_akt;
        pre>>stud_akt;
        for (int j=0; j<prze_count; j++){
            //int prze_akt;
            //pre>>prze_akt;
            int term_akt;
            int waga_akt;
            for (int k=0; k<term_count[j]; k++){
                pre>>term_akt;
                pre>>waga_akt;
                if ( waga_akt > pref_max )
                    pref_max = waga_akt;
                pref[stud_akt][term_akt] = waga_akt;
            }
        }
    }
    
    int kol_count;
    kol>>kol_count;
    
    //alokacja macierzy kolizji
    kolizje=new bool*[terms_total];
    for (int i=0; i<terms_total; i++)
        kolizje[i]=new bool[terms_total];
    
    for (int i=0; i<terms_total; i++)
        for (int j=0; j<terms_total; j++)
            kolizje[i][j]=false;
    
    for (int i=0; i<kol_count; i++){
        int term1, term2;
        kol>>term1;
        kol>>term2;
        kolizje[term1][term2] = true; //ustawiamy kolizje
        kolizje[term2][term1] = true;
    }
    
    int gro_count, gid = 1;
    
    gro >> gro_count >> total_groups_count;

    group = new int*[total_groups_count + 1];
    group[0] = new int(0); //grupa studentow bez grupy
    stud_group = new int*[prze_count];
    group_count = new int[prze_count];
    for ( int i = 0; i < prze_count; i++ ){
        stud_group[i] = NULL;
        group_count[i] = 0;
    }

//zalozenie: grupy sa uporzadkowane rosnaco po id przedmiotow
    for ( int i = 1; i <= gro_count; i++ ){
        int prze_id, prze_size;
        gro >> prze_id >> prze_size;
        group_count[prze_id] = prze_size;
        
        stud_group[prze_id] = new int[stud_count];
        for ( int j = 0; j < stud_count; j++ )
            stud_group[prze_id][j] = 0;
        
        for ( int j = 0; j < prze_size; j++ ){
            int group_size;
            gro >> group_size;
            group[gid] = new int[group_size + 1];
            group[gid][0] = group_size;
            for ( int k = 1; k <= group_size; k++ ){
                gro >> group[gid][k];
                stud_group[prze_id][ group[gid][k] ] = gid;
            }
            gid++;
        }
    }
    
    ter.close();
    pre.close();
    kol.close();
    gro.close();
    
/*    for (int i=0; i<stud_count; i++){
        cout<<i<<"\n";
        for (int j=0; j<prze_count*MAX_TERM; j++)
            cout<<"\t"<<j<<" "<<pref[i][j]<<"\n";
    }
*/
}

//USUWA LUDZI, KTORZY NIE ZAPISUJA SIE NA JAKIES PRZEDMIOTY
//FIXME: jesli ktos sie nie zapisuje na przedmiot, ale jest w jakiejs grupie,
//to bedzie kuku
void solution_trim(int** solution){
    for ( int i = 0; i < prze_count; i++ )
        for ( int k = 0; k < stud_count; k++ ){
            int j;
            for ( j = term_index[i]; j < term_index[i+1]; j++ )
                if ( pref[k][j] != 0 )
                    break;
            if ( j == term_index[i+1] ) //student nie zapisuje sie na zaden termin przedmiotu i
                solution[k][i] = -2;
        }
}

int random_term(int subj){
    return term_index[subj] + (int)floor(drand()*term_count[subj]);
}

//INICJALIZACJA ROZWIAZANIA
//FIXME: moze sie zakleszczac
bool solution_init_random(int** solution){    
    int* terminy = new int[terms_total];
    for ( int i = 0; i < terms_total; i++ )
        terminy[i] = terms[i];
        
    for ( int i = 0; i < stud_count; i++ )
        for ( int j = 0; j < prze_count; j++ )
            solution[i][j] = -1;        
        
    solution_trim(solution);

    for ( int sj = 0; sj < prze_count; sj++ ){
        int j = prze_order[sj];
        if ( stud_group[j] != NULL ){
        //najpierw zapisy ludzi, ktorzy sa w grupach
        //dzieki temu (raczej) nie bedzie sytuacji, gdzie dojdzie 
        //do zakleszczenia jakze prostego algorytmu
            for ( int si = 0; si < stud_count; si++ ){
                int i = stud_order[si];
                if ( solution[i][j] == -1 && stud_group[j][i] ){
                //wow, student jest w grupie
                    int gid = stud_group[j][i];
                    //znajdujemy termin, ktory pociagnie cala grupe
                    bool chosen = false;
                    int sel;
		    int reps = 0;
                    while ( !chosen ){
			if (reps > term_count[j] * prze_count)
			    return false;
                        sel = random_term(j);
                        if ( terminy[sel] >= group[gid][0] )
                            chosen = true;
			reps++;
                    }
                    //zapisujemy cala grupe
                    terminy[sel] -= group[gid][0];
                    for ( int k = 1; k <= group[gid][0]; k++ ){
                        if ( solution[ group[gid][k] ][j] == -2 ){
                            cerr << "Problem mamy :< " << endl;
                            exit(1);
                        }
                        solution[ group[gid][k] ][j] = sel;
                    }
                }
            }
        }
        for ( int si = 0; si < stud_count; si++ ){
            int i = stud_order[si];
            if ( solution[i][j] == -1 ){
                bool chosen = false;
                int sel;
                while ( !chosen ){
                    sel = random_term(j);
                    if ( terminy[sel] > 0 )
                        chosen = true;
                }
                terminy[sel]--;
                solution[i][j]=sel;
            }
        }
    }
    delete[] terminy;
    return true;
}

//PSEUDOLOSOWA LICZBA
double drand(){
    return (double)rand() / ((double)RAND_MAX + 1e-4);
}

//INICJALIZACJA FEROMONU ###################
void pheromone_init(double n){
    pheromones = new double* [stud_count];
    for ( int i = 0; i < stud_count; i++ ){
        pheromones[i] = new double[terms_total];
        for ( int j = 0; j < terms_total; j++ )
            pheromones[i][j] = n * max(0., (double)pref[i][j]);
    }
}

//ZWRACA PRZEDMIOT DO KTOREGO NALEZY TERMIN
int subject_of_term(int term){
    int l = 1;
    int r = prze_count;
    int i;
    do {
        i = (l + r) / 2;
        if (term_index[i] <= term)
            l = i + 1;
        else
            r = i;
    } while ( ! (term_index[i - 1] <= term && term_index[i] > term) );
    
    return i - 1;
}

//AKTUALIZACJA FEROMONU ####################
void pheromone_update(Ant& ant, double weight){
    for ( int i = 0; i < stud_count; i++ )
    for ( int j = 0; j < prze_count; j++ )
        if ( ant.solution[i][j] >= 0 )
            pheromones[i][ant.solution[i][j]] += weight * 
                    sqrt(max((double)ant.objective, 1./(fabs(ant.objective)+1.))) /
                            (double)stud_count;
}

//PAROWANIE FEROMONU #######################
void pheromone_evaporate(double rho){
    for ( int i = 0; i < stud_count; i++ )
        for ( int j = 0; j < terms_total; j++ )
            pheromones[i][j] *= (1 - rho);
}

//OBLICZANIE WSKAZNIKU POSTEPU #############
//alpha - wspolczynnik pamieci
void calculate_gpi(double* gpi, int last_best_obj, int new_best_obj, double alpha){
    *gpi = alpha * (*gpi) +    stud_count * (new_best_obj - last_best_obj) * 
            sqrt(max(new_best_obj, pref_max)) / sqrt(pref_max * stud_count * prze_count);
}

//POLEPSZENIE ROZWIAZANIA ZGODNIE Z FEROMONEM
//Losujemy studenta (grupe), ktoremu cos poprawiamy. Dla kazdego terminu
//losujemy liczbe z przedzialu od 1 - risk_const/sqrt(gpi + 1) do 1.
//risk_const powinno byc 0..1
void pheromone_improve(Ant& ant, double risk_const, int rep){
    int stud, maxi, minsi, mins, prze;
    double act, rand_min, rand_span;
    rand_min = 1 - risk_const/sqrt(gpi + 1);
    rand_span = 1 - rand_min;
    while ( rep-- ){
        stud = (int)floor(drand() * stud_count);
        double max = 0.;
        maxi = (int)floor(drand() * terms_total);
        //znajdujemy zamiane, ktora prawdopodobnie da calkiem niezle polepszenie
        for ( int i = 0; i < terms_total; i++ ){
            act = (drand() * rand_span + rand_min) * pheromones[stud][i];
            if ( act >= max ){
                maxi = i;
                max = act;
            }
        }
        prze = subject_of_term(maxi);
        if ( (maxi == ant.solution[stud][prze]) || (ant.solution[stud][prze] < 0) )
            continue;        
        //jesli na wybranym terminie jest wolne miejsce, to przepisujemy studenta
        //cerr << maxi << " " << ant.solution[stud][prze] << endl;                
        if ( ant.terms[maxi] > 0 ){
            ant.terms[maxi]--;
            ant.terms[ant.solution[stud][prze]]++;
            ant.solution[stud][prze] = maxi;
        } else { //coz, musimy kogos wywalic...
            mins = pref_max + 1;
            minsi = 0;
            //FIXME: szybsze wyszukiwanie studentow na terminie
            for ( int i = 0; i < stud_count; i++ )
                if ( ant.solution[i][prze] == maxi ){ // student z terminu maxi
                    if ( pref[i][maxi] < mins ){
                        mins = pref[i][maxi];
                        minsi = i;
                    }
                }
            //zamieniamy studentow terminami
            ant.solution[minsi][prze] = ant.solution[stud][prze];
            ant.solution[stud][prze] = maxi;
        }
    }
}

//LOKALNE PRZESZUKIWANIE ###################
void local_search(Ant& ant){
    randomize_array_order(prze_order, prze_count);
    randomize_array_order(stud_order, stud_count);
    randomize_array_order(stud_order2, stud_count);    
    for ( int ii = 0; ii < prze_count; ii++ ){
        //probujemy kazdemu studentowi poprawic dany przedmiot
        int i = prze_order[ii];
        for ( int ji = 0; ji < stud_count; ji++ ){
            int j = stud_order[ji];
            if ( ant.solution[j][i] < 0 )
                continue;
            for ( int ki = 0; ki < stud_count; ki++ ){
                int k = stud_order2[ki];
                if ( ant.solution[k][i] < 0 )
                    continue;                
                int dprefj = true_pref(ant.solution, j, ant.solution[k][i], ant.solution[j][i]) - 
                        true_pref(ant.solution, j, ant.solution[j][i], ant.solution[j][i]);
                int dprefk = true_pref(ant.solution, k, ant.solution[j][i], ant.solution[k][i]) - 
                        true_pref(ant.solution, k, ant.solution[k][i], ant.solution[k][i]);
                if ( dprefj > 0 && dprefk < 0 && ant.terms[ant.solution[k][i]] > 0 ){
                //przepisanie j do terminu k bedzie dobre, k do j juz nie, ale
                //k ma jeszcze wolne miejsca
                    //cerr << dprefj << endl;                    
                    ant.terms[ant.solution[k][i]]--;
                    ant.terms[ant.solution[j][i]]++;
                    ant.solution[j][i] = ant.solution[k][i];
                } else if ( dprefk > 0 && dprefj < 0 && ant.terms[ant.solution[j][i]] > 0 ){
                //odwrotnie
                    //cerr << dprefk << endl;
                    ant.terms[ant.solution[k][i]]++;
                    ant.terms[ant.solution[j][i]]--;
                    ant.solution[k][i] = ant.solution[j][i];
                } else if ( dprefk + dprefj > 0 ){//i tak zmiana sie oplaca
                    //cerr << dprefj + dprefk << endl;
                    int tmp = ant.solution[k][i];
                    ant.solution[k][i] = ant.solution[j][i];
                    ant.solution[j][i] = tmp;
                } 
            }
        }
    }
}

// LICZBA KOLIZJI Z DANYM TERMINEM W PLANIE DANEGO STUDENTA
int term_collides(int** plan, int stud_id, int term_in, int term_out){
    int result = 0;
    for ( int i = 0; i < prze_count; i++ )
        if ( plan[stud_id][i] != term_out && plan[stud_id][i] >= 0 && kolizje[term_in][plan[stud_id][i]] )
            result++;
    return result;
}

// LICZBA KOLIZJI W PLANIE STUDENTA stud_id
int has_collision(int** plan, int stud_id){
    int result = 0;
    for ( int j = 1; j < prze_count; j++ )
        for ( int k = 0; k < j; k++ )
            if ( plan[stud_id][j] >= 0 && 
                 plan[stud_id][k] >= 0 &&
                 kolizje[ plan[stud_id][j] ][ plan[stud_id][k] ] ){
                result++;
            }
    return result;
}

int true_pref(int** plan, int stud, int term_in, int term_out){
    return (pref[stud][term_in] ? pref[stud][term_in] : pref_max * -3) - 
            term_collides(plan, stud, term_in, term_out) * pref_max * prze_count -
            pref_max * 3 * group_split_diff(plan, stud, term_in, term_out);
}

int group_split_diff(int** plan, int stud, int term_in, int term_out){
    int prze = subject_of_term(term_in);
    if (!stud_group[prze] || !stud_group[prze][stud] || term_in == term_out )
        return 0;
    int group_id = stud_group[prze][stud];
    int people[terms_total];
    fill(people, people+terms_total, 0);
    for ( int i = 1; i <= group[group_id][0]; i++ ){
        people[ plan[ group[group_id][i] ][prze] ]++;
    }
    int max = 0, maxi;
    for ( int i = 0; i < terms_total; i++ )
        if ( people[i] > max){
            max = people[i];
            maxi = i;
        }
    if ( people[term_in] == max ){
        return -1; //split sie zmniejszy
    }
    if ( people[term_out] == max && people[term_in] < max-1 )
        return 1; //split sie zwiekszy
    return 0; //split sie nie zmieni
}

int groups_split(int** plan){
    int people[terms_total];
    int prze = 0;
    int result = 0;
    int cur_group_cnt = group_count[0];
    for ( int i = 1; i <= total_groups_count; i++ ){
        while (cur_group_cnt == 0){
            prze++;
            cur_group_cnt = group_count[prze];
        }
        cur_group_cnt--;
        
        fill(people, people+terms_total, 0);
        for ( int j = 1; j <= group[i][0]; j++ )
            people[ plan[ group[i][j] ][prze] ]++;
        int max = 0;
        for ( int j = 0; j < terms_total; j++ )
            if ( people[j] > max )
                max = people[j];
        result += group[i][0] - max;
    }
    return result;
}

//FCJA CELU ################################
int objective_function(int** plan){
    int gained = 0;
    for ( int i = 0; i < stud_count; i++ )
        for ( int j = 0; j < prze_count; j++ )
            if ( plan[i][j] >= 0 )
                gained += pref[i][plan[i][j]] ? pref[i][plan[i][j]] : pref_max * -3;
    // kolizje
    for ( int i = 0; i < stud_count; i++ )
        gained -= has_collision(plan, i) * pref_max * prze_count;
    gained -= 3 * pref_max * groups_split(plan);
    return gained;
}

//ZAPIS WYJSCIA ############################
void save_output(int** plan){

    ofstream out(outfile);

    int max=0;

    for (int i=0; i<stud_count; i++)
        for (int j=0; j<prze_count; j++){
            int max_local=0;
            
            for (int k = term_index[j]; k < term_index[j+1]; k++)
                if (pref[i][k]>max_local)
                   max_local=pref[i][k];
            max+=max_local;
        }
    
    int gained = objective_function(plan);
   
    for ( int i = 0; i < stud_count; i++ ){
        out << i << "\t\t";
        for ( int j = 0; j < prze_count; j++ )
            if ( plan[i][j] >= 0 )
                out << plan[i][j] << " ";
        out<<"\n";
    }
    
    out<<"\n\nWolne miejsca na terminach:\n";
    for (int i=0; i<terms_total; i++)
        if (best_so_far.terms[i]>0)
           out<<"#"<<i<<" "<<best_so_far.terms[i]<<"\n";
    
    out<<"\n\nOgolne zadowolenie: "<<gained<<"/"<<max;
    
    out.close();

//zapisujemy plan do pliku

//zwalniamy zaalokowana pamiec
}

// TWORZY LOSOWA PERMUTACJE TABLICY #####
void randomize_array_order(int* array, int n){
    int s, tmp;
    for ( int i = 0; i < n; i++ ){
        s = (int)floor(drand() * n);
        tmp = array[s];
        array[s] = array[i];
        array[i] = tmp;
    }
}

void ant_set(Ant& ant, int** solution){
    for ( int i = 0; i < terms_total; i++ )
        ant.terms[i] = terms[i];
    for ( int i = 0; i < stud_count; i++ ){
        for ( int j = 0; j < prze_count; j++ ){
            ant.solution[i][j] = solution[i][j];
            if ( solution[i][j] >= 0 )
                ant.terms[solution[i][j]]--;
        }
    }
    ant.objective = objective_function(ant.solution);    
    ant.best_objective = ant.objective;
    ant.lpi = stud_count * pref_max * prze_count;
}

// KOPIUJE PLAN DO MROWKI ###############
void ant_init(Ant& ant, int** solution){
    ant.terms = new int[terms_total];
    for ( int i = 0; i < terms_total; i++ )
        ant.terms[i] = terms[i];
    ant.solution = new int*[stud_count];
    for ( int i = 0; i < stud_count; i++ ){
        ant.solution[i] = new int[prze_count];
        for ( int j = 0; j < prze_count; j++ ){
            ant.solution[i][j] = solution[i][j];
            if ( solution[i][j] >= 0 )
                ant.terms[solution[i][j]]--;
        }
    }
    ant.objective = objective_function(ant.solution);
    ant.best_objective = ant.objective;
    ant.lpi = stud_count * pref_max * prze_count;
}

// MROWKOWY #############################
// eps - im mniejsze, tym wiecej iteracji
// risk_const - jak bardzo ryzykowne maja byc mrowki
// gpi_memory - jak bardzo wskaznik postepu ma pamietac poprzednie ulepszenia (im mniejszy, 
//                 tym algorytm szybciej sie zakonczy i szybciej bedzie bardziej agresywny)
// rho - wspolczynnik parowania feromonu
// dominant_ant_const - ile razy bardziej intensywny jest feromon dominujacej mrowki
void mrowkowy(Ant* ants, int n, double eps, double risk_const, double gpi_memory, double rho, 
        double dominant_ant_const){
    pheromone_init((double)n);
    gpi = stud_count * prze_count * pref_max;
    
    if ( !quiet )
    cerr << "GPI   BEST SOLUTION" << endl;
    
    while ( gpi > eps ){
        int maxobj = best_so_far.objective;
        int maxanti = -1;
        for ( int i = 0; i < n; i++ ){
            if ( ants[i].objective > maxobj ){
                maxanti = i;
                maxobj = ants[i].objective;
            }
        }
        calculate_gpi(&gpi, best_so_far.objective, maxobj, gpi_memory);
        if ( !quiet )
            cerr << gpi << " " << best_so_far.objective << endl;        
        if ( maxanti >= 0 )
            ant_set(best_so_far, ants[maxanti].solution);        
                
        for ( int i = 0; i < n; i++ ){
            local_search(ants[i]);
            local_search(ants[i]);
	    if ( ants[i].lpi <= stability_eps || i >= n*stable_ants_part )
        	pheromone_improve(ants[i], risk_const, reps);
        }
        pheromone_evaporate(rho);
        for ( int i = 0; i < n; i++ ){
            ants[i].objective = objective_function(ants[i].solution);       
            pheromone_update(ants[i], 1.);
            calculate_gpi(&ants[i].lpi, ants[i].best_objective, 
                    max(ants[i].best_objective, ants[i].objective), gpi_memory);
            ants[i].best_objective = max(ants[i].best_objective, ants[i].objective);
            if ( ants[i].lpi < rand_eps && i != maxanti ){
                randomize_array_order(stud_order, stud_count);
                if( drand() <= copy_pro )
		    ant_set(ants[i], best_so_far.solution);
		else {
		    while(!solution_init_random(ants[i].solution));
            	    ant_set(ants[i], ants[i].solution);
		}
            }
        }
        pheromone_update(best_so_far, dominant_ant_const - 1.);
        if (finishing){
            save_output(best_so_far.solution);
            exit(0);
        }
    }
}
